package Demo2;

public class demo4 {
    public void heapSort(int[] array) {
        for (int parent = (array.length - 1 - 1) / 2; parent >= 0; parent--) {
            makeHeap(array, parent, array.length);
        }

        int end = array.length - 1;
        while (end > 0) {
            swap(array, 0, end);
            makeHeap(array, 0, end);
            end--;
        }
    }

    private void makeHeap(int[] array, int parent, int length) {
        int child = 2 * parent + 1;
        while (child < length) {
            if (child + 1 < length && array[child] < array[child + 1]) {
                child++;
            }
            if (array[parent] < array[child]) {
                swap(array, parent, child);
                parent = child;
                child = 2 * parent + 1;
            } else {
                break;
            }
        }
    }

    private void swap(int[] array, int pos1, int pos2) {
        int temp = array[pos1];
        array[pos1] = array[pos2];
        array[pos2] = temp;
    }
}
